﻿/*=======================================================================================
	TASK 8:                                                                    {Arrays}
	Write a program that finds the sequence of maximal sum in given array.
    Example:{2, 3, -6, -1, 2, -1, 6, 4, -8, 8} => {2, -1, 6, 4}
	Can you do it with only one loop (with single scan through the elements of the array)?
========================================================================================*/

using System;

class MaximalSumWithOneLoop
{
    static void Main()
    {
        int[] arr = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
        //int[] arr = { 5, 2, -5, 3, 4 };

        int sum = 0;
        int maxSum = 0;
        int start = 0;
        int n = arr.Length;
        int k;
        int end=0;

        for ( k = 1; k < n; k++)
        {
            for (int i = 0; i <= n - k; i++)
            {
                for (int j = i; j < k + i; j++)
                {
                    sum = sum + arr[j];
                }
                if (sum > maxSum)
                {
                    maxSum = sum;
                    start = i;
                    end = start+k;
                }
                sum = 0;
            }
        }
        Console.WriteLine("maxSum={0}", maxSum);
        for (int i = start; i < end ; i++)
        {
            Console.Write(arr[i] + " ");
        }
//====================================================================== 
//        KADANE ALGORITHM

//        
//Ще направим задачата само с едно обхождане на масива. 
//Дефинираме като помощни променливи начало и край на редицата, максимална сума 
//и текуща сума (сумите инициализираме с първият елемент от масива). На всяка 
//итерация ако текущата сума е положителна, прибавяме към нея съответният елемент 
//от масива. Ако е станала отрицателна, взимаме за подредица само текущият елемент. 
//Ако сме получили сума, по-голяма от maxSum, презаписваме maxSum и пазим началото и края на подредицата.
//След като обходим масива остава с един цикъл от “началото” до “края”, които сме получили отпреди, да изпринтим на конзолата числата.
//======================================================================
        //int startIndex = 0;
        //int tempStartIndex = 0;
        //int endIndex = 0;
        //int currentSum = arr[0];
        //int maxSum = arr[0];

        //for (int i = 1; i < arr.Length; i++)
        //{
        //    currentSum =currentSum+ arr[i];

        //    if (arr[i] > currentSum)
        //    {
        //        currentSum = arr[i];
        //        tempStartIndex = i;
        //    }

        //    if (currentSum > maxSum)
        //    {
        //        maxSum = currentSum;
        //        startIndex = tempStartIndex;
        //        endIndex = i;
        //    }
        //}
        //for (int i = startIndex; i <= endIndex; i++)
        //{
        //    Console.Write("{0} ", arr[i]);
        //}
//======================================================================
    }
}

